#include "stdafx.h"
#include "PrimMinimumSpanningTree.h"
#include <iostream>
#include <algorithm>
#include <limits>

void PrimTree::CreateGraph(){
	graph_ = new Node*[node_num_];
	for(int i = 0; i < node_num_; ++i){
		std::cout << "input vec[" << i+1 << "]'s lable :" << std::endl;
		graph_[i] = new Node;
		std::cin >> graph_[i]->lable ;
		graph_[i]->key = std::numeric_limits<int>::max();
		std::cout << "input adjacency node count :" << std::endl;
		int cnt ;
		if(std::cin >> cnt){
			Node * p = graph_[i];
			for(int j = 0 ; j < cnt ; ++j){
				std::cout << "input vec[" << i+1 <<"]'s adjacecy node lable:" << std::endl;
				p->next = new Node;
				p = p->next;
				std::cin >> p->lable;
				std::cout << "input the weight :" << std::endl;
				int temp ;
				std::cin >> temp;
				weights_.push_back(std::make_pair(std::make_pair(graph_[i]->lable, p->lable),temp));		
			}
			p->next = NULL;
		}
	}
	//****** input instance*******
	/*graph_ = new Node*[9];

	graph_[0] = new Node;
	graph_[0]->lable = 'a';
	graph_[0]->key = std::numeric_limits<int>::max();
	Node *p = graph_[0];
	p->next = new Node;
	p = p->next;
	p->lable = 'b'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[0]->lable, p->lable),4));	
	p->next = new Node;
	p = p->next;
	p->lable = 'h'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[0]->lable, p->lable),8));	
	p->next = NULL;

	graph_[1] = new Node;
	graph_[1]->lable = 'b';
	graph_[1]->key = std::numeric_limits<int>::max();
	p = graph_[1];
	p->next = new Node;
	p = p->next;
	p->lable = 'a'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[1]->lable, p->lable),4));	
	p->next = new Node;
	p = p->next;
	p->lable = 'h'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[1]->lable, p->lable),11));
	p->next = new Node;
	p = p->next;
	p->lable = 'c';
	weights_.push_back(std::make_pair(std::make_pair(graph_[1]->lable, p->lable),8));
	p->next = NULL;

	graph_[2] = new Node;
	graph_[2]->lable = 'c';
	graph_[2]->key = std::numeric_limits<int>::max();
	p = graph_[2];
	p->next = new Node;
	p = p->next;
	p->lable = 'b'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[2]->lable, p->lable),8));	
	p->next = new Node;
	p = p->next;
	p->lable = 'i'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[2]->lable, p->lable),2));
	p->next = new Node;
	p = p->next;
	p->lable = 'f';
	weights_.push_back(std::make_pair(std::make_pair(graph_[2]->lable, p->lable),4));
	p->next = new Node;
	p = p->next;
	p->lable = 'd';
	weights_.push_back(std::make_pair(std::make_pair(graph_[2]->lable, p->lable),7));
	p->next = NULL;

	graph_[3] = new Node;
	graph_[3]->lable = 'd';
	graph_[3]->key = std::numeric_limits<int>::max();
	p = graph_[3];
	p->next = new Node;
	p = p->next;
	p->lable = 'c'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[3]->lable, p->lable),7));	
	p->next = new Node;
	p = p->next;
	p->lable = 'f'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[3]->lable, p->lable),14));
	p->next = new Node;
	p = p->next;
	p->lable = 'e';
	weights_.push_back(std::make_pair(std::make_pair(graph_[3]->lable, p->lable),9));
	p->next = NULL;

	graph_[4] = new Node;
	graph_[4]->lable = 'e';
	graph_[4]->key = std::numeric_limits<int>::max();
	p = graph_[4];
	p->next = new Node;
	p = p->next;
	p->lable = 'd'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[4]->lable, p->lable),9));	
	p->next = new Node;
	p = p->next;
	p->lable = 'f'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[4]->lable, p->lable),10));
	p->next = NULL;

	graph_[5] = new Node;
	graph_[5]->lable = 'f';
	graph_[5]->key = std::numeric_limits<int>::max();
	p = graph_[5];
	p->next = new Node;
	p = p->next;
	p->lable = 'e'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[5]->lable, p->lable),10));	
	p->next = new Node;
	p = p->next;
	p->lable = 'd'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[5]->lable, p->lable),14));
	p->next = new Node;
	p = p->next;
	p->lable = 'c';
	weights_.push_back(std::make_pair(std::make_pair(graph_[5]->lable, p->lable),4));
	p->next = new Node;
	p = p->next;
	p->lable = 'g';
	weights_.push_back(std::make_pair(std::make_pair(graph_[5]->lable, p->lable),2));
	p->next = NULL;

	graph_[6] = new Node;
	graph_[6]->lable = 'g';
	graph_[6]->key = std::numeric_limits<int>::max();
	p = graph_[6];
	p->next = new Node;
	p = p->next;
	p->lable = 'f'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[6]->lable, p->lable),2));	
	p->next = new Node;
	p = p->next;
	p->lable = 'i'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[6]->lable, p->lable),6));
	p->next = new Node;
	p = p->next;
	p->lable = 'h';
	weights_.push_back(std::make_pair(std::make_pair(graph_[6]->lable, p->lable),1));
	p->next = NULL;

	graph_[7] = new Node;
	graph_[7]->lable = 'h';
	graph_[7]->key = std::numeric_limits<int>::max();
	p = graph_[7];
	p->next = new Node;
	p = p->next;
	p->lable = 'b'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[7]->lable, p->lable),11));	
	p->next = new Node;
	p = p->next;
	p->lable = 'a'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[5]->lable, p->lable),8));
	p->next = new Node;
	p = p->next;
	p->lable = 'i';
	weights_.push_back(std::make_pair(std::make_pair(graph_[7]->lable, p->lable),7));
	p->next = new Node;
	p = p->next;
	p->lable = 'g';
	weights_.push_back(std::make_pair(std::make_pair(graph_[7]->lable, p->lable),1));
	p->next = NULL;

	graph_[8] = new Node;
	graph_[8]->lable = 'i';
	graph_[8]->key = std::numeric_limits<int>::max();
	p = graph_[8];
	p->next = new Node;
	p = p->next;
	p->lable = 'c'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[8]->lable, p->lable),2));	
	p->next = new Node;
	p = p->next;
	p->lable = 'g'; 
	weights_.push_back(std::make_pair(std::make_pair(graph_[8]->lable, p->lable),6));
	p->next = new Node;
	p = p->next;
	p->lable = 'h';
	weights_.push_back(std::make_pair(std::make_pair(graph_[8]->lable, p->lable),7));
	p->next = NULL;*/
}

int PrimTree::GetWeight(char a, char b){
	std::vector<cw_pair>::iterator it =
	std::find_if(weights_.begin(), weights_.end(), 
				std::bind2nd(pair_equal_op(), std::make_pair(a, b)));
	if(it == weights_.end()) return std::numeric_limits<int>::max();
	else return it->second;
}

PrimTree::~PrimTree(){
	for(int i = 0; i < node_num_; ++i){
		Node * p = graph_[i];
		for(;;){
			Node * del = p;
			if(del == NULL) break;
			p = p->next;
			delete del;
		}
	}
	delete [] graph_;
}

int PrimTree::LocateNode(char c){
	int index = -1;
	for(int i = 0; i < node_num_; ++i){
		if(graph_[i]->lable == c){
			index = i;
			break;
		}		
	}
	return index;
}
//the sort method influence the performence
int PrimTree::GetPrimTree(char d){
	int index = LocateNode(d);
	if(index == -1) return -1;
	int sum = 0;
	for(int i = 0; i < node_num_ ; ++i){
		que_.push_back(graph_[i]);	
	}
	graph_[index]->key = 0;
	
	for(;;){
		if(que_.empty()) break;
		que_.sort(less_key_cmp());//ensure that the minimum value is at the queue's head
		std::cout << que_.front()->lable << " ";
		sum += que_.front()->key;// accumulate the value
		Node * p = que_.front()->next;//adjacency node point
		int p_index = LocateNode(que_.front()->lable);//the output node index
		que_.pop_front();
		//update the output's adjacency node value
		for(;;){
			if(p == NULL) break;
			int child_index = LocateNode(p->lable);
			int w = GetWeight(graph_[p_index]->lable, p->lable);
			if(graph_[child_index]->key > w )//if less than child to tree's weight which is already known then upadte
				graph_[child_index]->key = w;//also can add his parent's node relationship
			p = p->next;
		}
	}
	std::cout<< std::endl;
	return sum;
}